1. Field of the Invention
The present invention relates generally to point cloud data, and in particular, to a method, apparatus, and article of manufacture for approximating the outline of buildings and structures from a point cloud.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by references enclosed in brackets e.g., [x]. Such references may indicate the first named authors and year of publication e.g., [Jones 2002]. A list of these different publications ordered according to these references can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Building information models (BIM) are being increasingly used throughout a building's lifecycle in the Architecture, Engineering and Construction (AEC) industry. BIM models can be used for many purposes, from planning and visualization in the design phase, to inspection during the construction phase, and to energy efficiency analysis and security planning during the facility management phase. However, no design BIM exists for most existing buildings. Further, the BIM created at design time may vary significantly from what is actually built. As a result, there is an increasing interest in creating BIMs of the actual as-built building.
Laser scanners are rapidly gaining acceptance as a tool for 3D modeling and analysis in the architecture, engineering and construction (AEC) domain. With technological development/evolution, laser scanners are capable of acquiring range measurements at rates of tens to hundreds of thousands of points per second, at distances of up to a few hundred meters, and with measurement error on the scale of millimeters [Huber 2010], which make them well suited to densely capturing the as-built information of building interiors and exteriors. Usually, multiple scans are needed to capture the point cloud of a whole building. Laser scanners are placed in various locations throughout and around a building. The scans from each location are registered and aligned to form a point cloud in a common coordinate system.
Currently, as-built BIMs are mostly created interactively form the point cloud data from laser scanners. This creation process is labor-intensive and error-prone. Software tools for processing point clouds have attempted to improve the ability to handle the enormous point clouds produced by laser scanners and to integrate the use of point cloud data into BIM modeling software. Geometric surface or volumetric primitives can be fitted to the 3D point cloud to model walls, floors, ceilings, columns, beams and other structures of interest.
In view of the above, it may be desirable to model a polyline boundary of points from a building scan. However, a boundary determination based on points obtained via a scan of a building is a crucial and difficult step in the building reconstruction task. One reason for the difficulty is that laser scanners have some difficulty in the as-built environment to capture low-reflectance surfaces (e.g., anything painted black), specular surfaces (e.g., shiny metal and mirrors), and transparent or translucent surfaces (e.g. windows), which results in the presence of concavity in the building boundary [Huber 2010]. Moreover, point clouds are often composed of multiple scans with noise and points of non-uniform point density, which will also cause difficulty in a boundary determination. Such problems may be better understood with an explanation of prior art techniques that have attempted boundary extraction.
One category of boundary extraction is purely based on computational geometry methods. [Jarvis 1977] modifies the convex hull formation algorithm to limit the searching space to a certain neighborhood. However, this approach is not very successful in experiments because the distribution of the used points is far from even. [Edelsbrunner 1994] described a so-called alpha-shape determination algorithm, where the shape of a point set is defined as the intersection of all closed discs with radii. This method is computationally complex, and its performance depends on the parameter alpha. Although methods for line simplification (such as Douglas-Peucker) can be applied during the generalization process, this category of boundary extraction methods doesn't take the regular shape characteristics existing in most common buildings into consideration, and thus cannot generate satisfying outline results that can be used for as-built building modeling.
In the last few decades, considerable research effort has been directed toward mainly building outline generation, but most of the prior art is focused on reconstructing building models using aerial imagery and airborne laser scanning data.
In order to generalize the building outline, [Maas & Vosselman 1999] determined the ridge line as a horizontal intersection between roof faces and then use the direction of the ridge line as an approximation for the main direction of the building. [Dutter 2007] starts with an MBR (Minimum Bounding Rectangle) and determines relevant deviations from the rectangle lines. This is done recursively, thus enabling different shapes of buildings like L, T or U-shaped outlines, which limits the generality of Dutter's method. [Shan & Sampath 2007] use straight lines in the main direction of the buildings to approximate the shape and then use least squares adjustment for the adaptation to the original boundary points. [Sester and Neidhart 2008] employ a RANSAC (RANdom Sample Consensus) method to generate a set of initial line hypotheses firstly, and the hypotheses are refined using a least squares adjustment process in which the segments are shifted to fit the original shape and to enforce relations between segments.
[Jwa et al. 2008] rectified noisy polyline by re-arranging quantized line slopes in a local shape configuration and globally selecting optimal outlines based on the Minimum Description Length principles. [Dorninger and Pfeifer 2008] define a coarse approximation of the outline by the computation of a 2D alpha-shape of all the given points and the post-processing of the alpha-shape polygon by a generalization and regularization process. [Guercke and Sester 2011] sample the outline of the polygon into small line segments in a first step and then transform the line segments into Hough space. The lines corresponding to the peaks in the Hough buffer are used to generate initial hypotheses for the polygon outline which is refined by a least squared adjustment procedure to enforce parallel or perpendicular segments.
In view of the above, it is desirable to extract/determine boundaries from building point cloud data in an easy and efficient manner.